package main

// 4. 寻找两个正序数组的中位数
func main() {
	num1 := []int{1, 2}
	num2 := []int{3, 4}
	arrays := findMedianSortedArrays(num1, num2)
	println(arrays)

}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	// 简单处理先跳过，合并数组再找中间数据
	nums1Len := len(nums1)
	nums2Len := len(nums2)

	newArr := make([]int, nums1Len+nums2Len)

	newPoint := 0
	point1 := 0
	point2 := 0

	for point1 < nums1Len || point2 < nums2Len {
		if point1 == nums1Len {
			newArr[newPoint] = nums2[point2]
			point2++
		} else if point2 == nums2Len {
			newArr[newPoint] = nums1[point1]
			point1++
		} else if nums1[point1] < nums2[point2] {
			newArr[newPoint] = nums1[point1]
			point1++
		} else {
			newArr[newPoint] = nums2[point2]
			point2++
		}
		newPoint++
	}

	mid := (nums1Len + nums2Len) / 2
	if (nums1Len+nums2Len)%2 == 0 {
		return float64(newArr[mid-1]+newArr[mid]) / 2
	}

	return float64(newArr[mid])
}

// 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
//
//算法的时间复杂度应该为 O(log (m+n)) 。
//
//示例 1：
//
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
//示例 2：
//
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
//
//提示：
//
//nums1.length == m
//nums2.length == n
//0 <= m <= 1000
//0 <= n <= 1000
//1 <= m + n <= 2000
//-106 <= nums1[i], nums2[i] <= 106
